package algorithm.tree;

import algorithm.linear.LinkedQueue;
import algorithm.linear.LinkedStack;

/**
 * 二叉树类
 * @param <E>
 */
public class BinaryTree<E> {
    //根节点
    protected BinaryNode<E> root;

    private int i = 0;

    public BinaryTree () {
        root = null;
    }

    public BinaryTree(BinaryNode root){
        this.root = root;
    }

    //以空子树的先根序列构造一棵二叉树
    public BinaryTree(E[] preoder) {
        root = create(preoder);
    }

    public boolean isEmpty() {
        return this.root == null;
    }

    public BinaryNode getRoot() {
        return this.root;
    }

    public void preOrder() {
        System.out.println("\n 先根序列：");
        preOrder(root);
    }

    public void preOrder(BinaryNode p) {
        if( p != null ) {
            System.out.println(p.data);
            preOrder(p.left);
            preOrder(p.right);
        }
    }

    public void inOrder() {
        System.out.println("\n 中根序列：");
        inOrder(root);
    }

    public void inOrder(BinaryNode p) {
        if (p!=null) {
            inOrder(p.left);
            System.out.println(p.data);
            inOrder(p.right);
        }
    }

    public void postOrder() {
        System.out.println("\n 后根序列：");
        postOrder(root);
    }

    public void postOrder(BinaryNode p) {
        if (p!=null) {
            postOrder(p.left);
            postOrder(p.right);
            System.out.println(p.data);
        }
    }
    //结点个数
    public int count() {
        return count(root);
    }
    public int count(BinaryNode p){
        if (p!=null)
            return 1+count(p.left)+count(p.right);
        else
            return 0;
    }
    //求高度
    public int height() {
        return height(root);
    }
    public int height(BinaryNode p){
        if (p!=null) {
            int id = height(p.left);
            int rd = height(p.right);
            return id >= rd ?id+1 :rd +1;
        }
        else
            return 0;
    }
    //查找
    public BinaryNode search(E value) {
        return search(root,value);
    }
    //在以P为根的子树中查找值为value的结点，先根次序遍历
    public BinaryNode search(BinaryNode p, E value){
        //找到value值的结点
        BinaryNode find = null;
        if (p!=null && value !=null) {
            if(p.data.equals(value)) {
                //查找成功
                find = p;
            } else {
                //在左子树中查找
                find = search(p.left,value);
                if(find == null){
                    //若左子树中没有找到，继续去右子树中查找
                    find = search(p.right,value);
                }
            }
        }
        return find;
    }
    //获得父母结点
    public BinaryNode getParent(BinaryNode node) {
        if (root == null || node == null || root==node){
            return null;
        }
        return getParent(root,node);
    }
    public BinaryNode getParent(BinaryNode p,BinaryNode node) {
        BinaryNode find = null;
        if (p!=null){
            //查找成功
            if (p.left == node|| p.right==node) {
                find = p;
            } else {
                find = getParent(p.left,node);
                if (find ==null) {
                    find = getParent(p.right,node);
                }
            }
        }
        return find;
    }
    //创建一棵子树，当前结点是preoder[i],返回所创建子树的根结点
    private BinaryNode create(E[] preorder) {
        BinaryNode p = null;
        if(i<preorder.length){
            E elem = preorder[i];
            i++;
            if (elem != null) {
                p = new BinaryNode(elem); //建立p结点
                p.left = create(preorder);
                p.right = create(preorder);
            }
        }
        return p;
    }
    //插入一个结点
    public void insert(BinaryNode<E> p,E element,boolean leftChild ) {
        if(p != null ){
            if ( leftChild ) {
                p.left = new BinaryNode<E>(element,p.left,null);
            } else {
                p.right = new BinaryNode<E>(element,null,p.right);
            }
        }
    }
    //插入元素element作为p结点的左孩子
    public void insert(BinaryNode<E> p, E element) {
        insert(p,element,true);
    }
    //删除p结点的左、右子树，若leftChild为true,删除左子树，否则删除右子树
    public void remove(BinaryNode<E> p, boolean leftChild) {
        if (p!=null) {
            if(leftChild){
                p.left = null;
            } else {
                p.right = null;
            }
        }
    }
    //删除P结点的左子树
    public void remove(BinaryNode p) {
        remove(p,true);
    }
    //中根次序遍历二叉树的非递归算法
    public void inOrderTraverse() {
        System.out.println("中根次序遍历二叉树的非递归算法:");
        LinkedStack<BinaryNode<E>> stack = new LinkedStack<BinaryNode<E>>();
        BinaryNode<E> p = this.root;
        while(p!=null || !stack.isEmpty()) {
            if(p!=null){
                stack.push(p);//p入栈
                p = p.left;//进入左子树
            }
            else {
                p = stack.pop();//p指向出栈的结点
                System.out.println(p.data);//访问结点
                p = p.right;//进入右子树
            }
        }
    }
    //按层次遍历二叉树
    public void levelOrder() {
        LinkedQueue<BinaryNode<E>> que = new LinkedQueue<BinaryNode<E>>();
        BinaryNode<E> p = this.root;
        System.out.println("遍历层次：");
        while(p!=null){
            System.out.println(p.data);
            if(p.left!=null){
                que.enqueue(p.left);//左子树入队
            }
            if(p.right!=null){
                que.enqueue(p.right);//右子树入队
            }
             p = que.dequeue();//p指向队列的结点
        }
        System.out.println(que);
    }
}
